#include "stdc/stdc++.h"
using namespace std;

class Solution
{

   public:
    int countSeniors(std::vector<std::string> &details)
    {
        int count = 0;
        for (auto detail : details)
        {
            if (detail.size() >= 15)
            {
                if ((detail[11] > '6') || (detail[11] == '6' && detail[12] > '0'))
                {
                    count++;
                }
            }
        }
        return count;
    }
    int countDigits(int num)
    {
        int count = 0;
        for (auto str : std::to_string((int)num))
        {
            int digit = str - '0';
            if (0 == num % digit)
            {
                count++;
            }
        }
        return count;
    }

    /**
     * @brief 矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
        horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离
        verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离
        请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其
        面积。由于答案可能是一个很大的数字，因此需要将结果 对 109 + 7 取余 后返回。
     */
    int maxArea(int h, int w, vector<int> &horizontalCuts, vector<int> &verticalCuts)
    {
        std::sort(horizontalCuts.begin(), horizontalCuts.end());
        std::sort(verticalCuts.begin(), verticalCuts.end());

        int h_max = horizontalCuts[0];
        int h_size = horizontalCuts.size();
        for (int i = 1; i < h_size; i++)
        {
            int h = horizontalCuts[i] - horizontalCuts[i - 1];

            h_max = (h_max > h) ? (h_max) : (h);
        }
        h_max = (h_max > (h - horizontalCuts[h_size - 1])) ? (h_max) : (h - horizontalCuts[h_size - 1]);

        int v_max = verticalCuts[0];
        int v_size = verticalCuts.size();
        for (int i = 1; i < v_size; i++)
        {
            int h = verticalCuts[i] - verticalCuts[i - 1];

            v_max = (v_max > h) ? (v_max) : (h);
        }
        v_max = (v_max > (w - verticalCuts[v_size - 1])) ? (v_max) : ((w - verticalCuts[v_size - 1]));

        std::cout << h_max << " " << v_max << std::endl;
        // 1ll 表示一个 long long 类型的整数常量。在这里，ll 是用来指示编译器将数字 1 解释为 long long 类型，而不是默认的 int 类型
        return (1ll * h_max * v_max) % (long long)(1e9 + 7);
    }

    long long pickGifts(vector<int> &gifts, int k)
    {
        while (k--)
        {
            std::sort(gifts.begin(), gifts.end(), std::greater<int>());
            gifts[0] = (int)sqrt(gifts[0]);
        }

        return accumulate(gifts.begin(), gifts.end(), 0ll);
    }

    /**
     * @brief
        make_heap()将区间内的元素转化为heap.
        push_heap()对heap增加一个元素.
        pop_heap()对heap取出下一个元素.
        sort_heap()对heap转化为一个已排序群集.

        is_heap 测试范围内的元素是否是一个二叉堆 c++11
        is_heap_until 该函数返回有效二叉堆的最末范围。如果都有效，则返回last.也就是说，返回第一个破坏二叉堆结构元素的迭代器。c++11
     */
    long long pickGifts_01(vector<int> &gifts, int k)
    {
        // 最大堆：父结点的键值总是大于或等于任何一个子节点的键值
        // make_heap(gifts.begin(), gifts.end(),less<int>());
        // 最小堆：父结点的键值总是小于或等于任何一个子节点的键值
        // make_heap(gifts.begin(), gifts.end(),greater<int>());

        make_heap(gifts.begin(), gifts.end());
        while (k--)
        {
            gifts[0] = (int)(sqrt(gifts[0]));
            make_heap(gifts.begin(), gifts.end());
        }
        return accumulate(gifts.begin(), gifts.end(), 0ll);
    }

    long long pickGifts_02(vector<int> &gifts, int k)
    {
        make_heap(gifts.begin(), gifts.end());
        while (k--)
        {
            pop_heap(gifts.begin(), gifts.end());
            *gifts.rbegin() = (int)(sqrt(*gifts.rbegin()));
            push_heap(gifts.begin(), gifts.end());
        }
        return accumulate(gifts.begin(), gifts.end(), 0ll);
    }
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> result{};

        if (nullptr == root)
            return result;

        std::queue<TreeNode *> Queue;
        Queue.push(root);

        while (!Queue.empty())
        {
            vector<int> level;
            int currentLevelSize = Queue.size();
            for (int i = 0; i < currentLevelSize; i++)
            {
                TreeNode *node = Queue.front();
                Queue.pop();
                level.push_back(node->val);
                if (node->left != nullptr)
                {
                    Queue.push(node->left);
                }
                if (node->right != nullptr)
                {
                    Queue.push(node->right);
                }
            }
            result.push_back(level);
        }

        return result;
    }
};